﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>


//void _Catego(int* a, int begin, int end, int* copy)
//{
//	if (begin >= end)
//		return;
//
//		int i = begin;
//		int mid = (begin + end) / 2;
//		_Catego(a, begin, mid, copy);
//		_Catego(a, mid+1, end, copy);
//
//		int begin1 = begin; int end1 = mid;
//		int begin2 = mid+1;  int end2 = end;
//		while (begin2 <= end2 && begin1 <= end1)
//		{
//			if (a[begin1] > a[begin2])
//			{
//				copy[i++] = a[begin2++];
//			}
//			else
//			{
//				copy[i++] = a[begin1++];
//			}
//		}
//
//		while (begin2 <= end2)
//		{
//			copy[i++] = a[begin2++];
//		}
//
//		while (begin1 <= end1)
//		{
//			copy[i++] = a[begin1++];
//		}
//	memcpy(a + begin, copy + begin, sizeof(int) * (end - begin + 1));
//}
//
//
//void CategoSort(int* a, int n)
//{
//	int* copy = (int*)malloc(sizeof(int) * n);
//	if (copy == NULL)
//	{
//		perror("malloc");
//		return;
//	}
//
//	_Catego(a, 0, n-1, copy);
//	free(copy);
//}

/*
     解题思路：
       1. 设置一个计数，记录从前往后遍历时遇到的不同元素的个数
          由于不同的元素需要往前搬移，那count-1就是前面不同元素
          搬移之后，最后一个元素的位置，下一次在遇到不同元素就应该
          搬移到count位置
       2. 遍历数组，如果nums[i]与nums[count-1]不等，就将nums[i]搬移
          到nums[count]位置，不同元素多了一个，给count++
       3. 循环结束后，返回count
*/

//﻿int removeDuplicates(int* nums, int numsSize) {
//    int count = 0;
//    for (int i = 1; i < numsSize; ++i)
//    {
//        if (nums[i] != nums[count])
//            nums[++count] = nums[i];
//    }
//
//
//    ++count;
//    return count;
//}

////int removeDuplicates(int* nums, int numsSize) {
////
////    int i = 0;
////    int j = 1;;
////    while (i < numsSize)
////    {
////        while (i < numsSize && nums[i] == nums[i + 1])
////        {
////            i++;
////        }
////        if (i == numsSize-1)
////        {
////            nums[j] = '\0';
////            break;
////        }
////        if (i < numsSize)
////        {
////            nums[j++] = nums[i + 1];
////            i++;
////        }
////       
////    }
////    return j;
////}

//int removeDuplicates(int* nums, int numsSize) {
//
//    int i = 0;
//    int j = 1;;
//    while (i < numsSize)
//    {
//        if (i == numsSize - 1)
//        {
//            break;
//        }
//
//        while (i < numsSize && nums[i] == nums[i + 1])
//        {
//            i++;
//        }
//        if (i == numsSize - 1)
//        {
//            break;
//        }
//
//        if (i < numsSize)
//        {
//            nums[j++] = nums[i + 1];
//            i++;
//        }
//
//    }
//    return j;
//}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    if (m == 0 && n == 0)
        return;
    if (n == 0)
        return;

    int fast = m - n - 1; int slow = n - 1;
    while (fast >= 0 && slow >= 0)
    {
        if (nums1[fast] >= nums2[slow])
        {
            nums1[m - 1] = nums1[fast];
            fast--;
        }
        else
        {
            nums1[m - 1] = nums2[slow];
            slow--;
        }
        m--;
    }

}
 
int main()
{
    int nums1[] = { 1,2,3,0,0,0 };
    int nums2[] = { 2,5,6 };
    int m = sizeof(nums1) / sizeof(nums1[0]);
    int n = sizeof(nums2) / sizeof(nums2[0]);

    //removeDuplicates(nums, sz);
    merge(nums1, m - n, m, nums2, n, n);

    return 0;
}